「CEOI2020」象棋世界

Posted on Edited on In

「CEOI2020」象棋世界

下文默认 \(n=R,m=C,x=c_1,y=c_R\)

Pawn

略

Rook

略

Queen

先判掉一次到达的情况，然后就可以从起点和终点分别画出5条可行线

由此得到若干交点，手动数一下有几个交点在内部的整点上

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void QQQ(){
	int d=abs(x-y);
	if(d==n-1 || d==0) puts("1 1"); // 一次到达
	else {
		d=(n-1-d)/2;
		int res=4;
		if(n==m) {
            // 一条斜着，一条平着
			if(x==1 || x==n) res++;
			if(y==1 || y==n) res++;
		}
		if(((x+1)&1)==((y+n)&1)) { // 先判断整点，然后判断两条斜线相交是否在内部
			if(min(x,y)-d>=1) res++;
			if(max(x,y)+d<=m) res++;
		}
		printf("%d %d\n",2,res);
	}
}

\[ \ \]

\[ \ \]

Bishop

看起来是很复杂的问题，但是实际上可以从一个简单的贪心入手

判定条件

可以发现，任意一次行走的直线上，坐标 \((x,y)\) 的 \((x+y)\mod 2\) 不变

所以只要 \(x+1\equiv y+n\pmod 2\) 即可

贪心策略

首先一定是每次向前走

第一步选择向左/右，然后每次转向，每次走都顶到边界线

但是这样显然会无法到达最终位置

纠正方法

考虑贪心到达的最后位置为 \(to\) ，那么得到的差值 \(|to-y|\) 是我们要矫正的距离

而矫正方法：在中途出现的每次转向位置，向里面"凹"进去一点，每凹进去一格，实际上相当于少走了两格

注意矫正的方向是根据最后一步走的方向而变化的，因此如果矫正方向不对，需要额外增加一步

此时，相当于需要多矫正到沿边界线对称的位置，需要多走 \(2(to-1)\) 或者 \(2(m-to)\) 的距离

假设走了 \(c\) 步，那么我们有 \(c-1\) 个转折点，最后将这若干的矫正距离分配到 \(c-1\) 个转折点上，可以用一个组合数解决

由于矫正距离是 \(O(m)\) 的，所以组合数显然可以在 \(O(m)\) 时间内求出

\[ \ \]

最后将向左向右合并即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
ll qpow(ll x,ll k=P-2) {
	ll res=1;
	for(;k;k>>=1,x=x*x%P) if(k&1) res=res*x%P;
	return res;
}
int C(int n,int m) {
	if(m>n-m) m=n-m;
	int a=1,b=1;
	rep(i,1,m) a=1ll*a*(n-i+1)%P,b=1ll*b*i%P;
	return a*qpow(b)%P;
}
int Divide(int n,int m){ // Divide n elements in to m groups , each can be empty
	if(m<=0 && n>0) return 0;
	return C(n+m-1,m-1);
}
void BBB(){
	if(((x+1)&1)!=((y+n)&1)) return puts("0 0"),void();
	auto Subsolver=[&](int x,int y){
        // assume that we go left first
		int c=0,to=x,dis=n-1; // count , towardsposition
		c=1,dis-=x-1,to=1; // go left by x-1
		c+=dis/(m-1),to=((dis/(m-1))&1)?m:1,dis%=m-1; // then each step m-1 opposite
		if(dis) c++,to=to==1?to+dis:to-dis; // reach destination (NO!)
		if(to==y) return mp(c,1);
		int d=abs(to-y)/2;
		if((c&1)  && y>to) d+=to-1,c++;
		if((~c&1) && y<to) d+=m-to,c++;
		return mp(c,Divide(d,c-1));
	};
	Pii l=Subsolver(x,y),r=Subsolver(m-x+1,m-y+1);
	if(l.first>r.first) swap(l,r);
	if(r.first==l.first) (l.second+=r.second)%=P;
	printf("%d %d\n",l.first,l.second);
}

\[ \ \]

\[ \ \]

King

可以发现，每次一定是向前的三个方向走，由此可以得到一个简单的 $O(nm)$ \(dp\)

用矩阵优化可以做到 \(O(m^3\log n)\) 求出所有的答案

难点在于如果快速求出这个矩阵 \(A\) 的 \(A^{n-1}\) ，即要加速矩阵求幂

容易想到用 特征多项式 解决该问题，参考

问题分为两步

得到 \(p_m(\lambda)\)

列出我们的转移矩阵 \(A=\)

\(\begin{matrix}1\ 1\ 0\ 0\ 0\ 0\ \cdots \ 0\\ 1\ 1\ 1\ 0\ 0\ 0\ \cdots \ 0\\ 0\ 1\ 1\ 1\ 0\ 0\ \cdots \ 0\\ \cdots\cdots\cdots\cdots \\ 0\ \cdots\ 0\ 0\ 1\ 1\ 1\ 0\\0\ \cdots\ 0\ 0\ 0\ 1\ 1\ 1\\ 0\ \cdots\ 0\ 0\ 0\ 0\ 1 \ 1\end{matrix}\)

\(\lambda I-A=\)

\(\lambda -1\) \(-1\) \(0\) \(0\) \(0\) \(0\) \(\cdots\) \(0\)
\(-1\) \(\lambda -1\) \(-1\) \(0\) \(0\) \(0\) \(\cdots\) \(0\)
\(0\) \(-1\) \(\lambda -1\) \(-1\) \(0\) \(0\) \(\cdots\) \(0\)
\(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\) \(\cdots\)
\(0\) \(0\) \(\cdots\) \(0\) \(-1\) \(\lambda -1\) \(-1\) \(0\)
\(0\) \(0\) \(\cdots\) \(0\) \(0\) \(-1\) \(\lambda -1\) \(-1\)
\(0\) \(0\) \(\cdots\) \(0\) \(0\) \(0\) \(-1\) \(\lambda -1\)

每一行有 \(2/3\) 个元素，看起来并不是很好得到行列式

但是容易得到一个递推式，设 \(m\) 阶转移矩阵的特征多项式为 \(p_m(\lambda)\)

如果最后一行取第 \(m\) 个元素，值为 \((\lambda-1)p_{m-1}(\lambda)\)

如果最后一行取第 \(m-1\) 个元素，值为 \(-p_{m-2}(\lambda)\)

因而得到

\(p_m(\lambda)=\left\{\begin{aligned}1&& m=0\\ \lambda-1 && m=1\\ (\lambda-1)p_{m-1}(\lambda)-p_{m-2}(\lambda) && m>1\end{aligned}\right.\)

可以在 \(O(m^2)\) 的时间内暴力求出，也可以得到通项公式(太憨了)

那么得到关系用 \(\lambda^n\mod p_m(\lambda)\) 的系数优化计算，可以用暴力实现的多项式取模+快速幂得到 \(O(m^2\log n)\)

当然也可以优化

\[ \ \]

求出 \(A^0,A^1,A^2\cdots A^m\)

直接求显然是 \(O(m^3)\) 的，卡一卡说不定能过？

由于走的是一个 \(m\times m\) 的棋盘，可以用一个简单容斥得到答案

设 \(f_{x,y}\) 为从 \(x\) 走到 \(y\) ，中途允许超出边界的方案数

由于棋盘只有 \(m\times m\) ，中途最多只会可能经过一条边界线

而一旦在某一个时刻超出边界线到达 \(0/m+1\) ，那么接下来达到这条边界线两侧对称点的方案数是一样的

即：跨过了某一条边界线 \(0/m+1\) 的不合法方案数，可以用到达 \(y\) 关于这条边界线的 对称点的 不一定合法方案数得到

而不一定合法的 \(f_{x,y}\) 实际上只和 \(|x-y|\) 有关

由此，可以用 \(f_{0,i}\) 表示出 \(A^i_{x,y}\) ，那么接下来只需要先计算出 \(f_{0,i}\) 对于系数的求和，最终进行一次容斥，减去两侧不合法方案数即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
typedef vector <int> Poly;
Poly operator * (const Poly &a,const Poly &b){
	int n=a.size()-1,m=b.size()-1;
	Poly c(n+m+1);
	rep(i,0,n) rep(j,0,m) c[i+j]=(c[i+j]+1ll*a[i]*b[j])%P;
	return c;
}
Poly operator * (Poly a,const int &b){
	for(int &i:a) i=1ll*i*b%P;
	return a;
}
Poly operator + (Poly a,const Poly &b){
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]+=b[i],Mod1(a[i]);
	return a;
}
Poly operator - (Poly a,const Poly &b){
	if(a.size()<b.size()) a.resize(b.size());
	rep(i,0,b.size()-1) a[i]-=b[i],Mod2(a[i]);
	return a;
}
Poly operator % (Poly a,const Poly &b){
	int n=a.size()-1,m=b.size()-1;
	if(n<m) return a;
	assert(b[m]==1);
	drep(i,n-m,0) rep(j,0,m) a[i+j]=(a[i+j]+1ll*(P-a[i+m])*b[j])%P;
	a.resize(m);
	return a;
}
Poly Pow(Poly x,int k,Poly Mod){
	Poly res=x; k--;
	for(;k;k>>=1,x=x*x%Mod) if(k&1) res=res*x%Mod;
	return res;
}

Poly F,G,T=Poly{P-1,1};
int f[N*2],g[N*2],H[N*2];
void KKKInit(){
	G=Poly{1},F=T;
	rep(i,2,m) swap(F,G),F=G*T-F; // 递推特征多项式
	F=Pow(Poly{0,1},n-1,F); // 求出x^{n-1} mod p(x)
	f[0]=1,H[0]=F[0];
	rep(t,1,F.size()-1) { // 求出f_{0,i}，只需要求一半
		rep(i,0,t) g[i]=f[i];
		rep(i,0,t) {
			f[i]=(0ll+(i?g[i-1]:g[1])+g[i]+g[i+1])%P;
			H[i]=(H[i]+1ll*f[i]*F[t])%P; // 乘上系数累和
		}
	}
}
void KKK(){
	int res=H[abs(x-y)];
    // 两侧对称点
	// y -> 0-(y-0)=-y
	// y -> m+1+(m+1-y)=2(m+1)-y
	res-=H[abs(-y-x)];
	res-=H[abs(2*(m+1)-y-x)];
    // 容斥
	res=(res%P+P)%P;
	printf("%d %d\n",n-1,res);
}